#include "set.h"



/************************************************************************
Theset_create operation initializes a set so that it can be used in other operations
(see Example 7-2). Since a set is a linked list, list_create is called to initialize it. The
match member is set to match by hand because this member is not used by
linked lists and is therefore not set by list_create.
The runtime complexity ofset_createis the same as list_create, or O(1).
************************************************************************/
Set* set_create(int (*match)(const void* key1, const void* key2), \
			  void (*destroy)(void* data))
{
	Set* set;
	set = list_create(destroy);
	list_set_match(set, match);

	return set;
}
/************************************************************************
The set_destroy operation destroys a set (see Example 7-1). Since a set is a linked
list and requires being destroyed in the same manner, set_destroyis defined to list_
destroy.
The runtime complexity ofset_destroyis the same as list_destroy,orO(n), wheren
is the number of members in the set.
************************************************************************/
void set_destroy(Set* set)
{
	list_destroy(set);
}
/************************************************************************
Theset_insert operation inserts a member into a set (see Example 7-2). Since a
member must not occur more than once in a set,set_is_member is called to make
sure that the set does not already contain the new member. As long as the member
does not already exist in the set,list_ins_nextis called to insert the member.
The runtime complexity ofset_insert is O(n) because set_is_member runs in O(n)
time, and list_ins_nextruns inO(1).
************************************************************************/
int set_insert(Set* set, const void* data)
{

	if (set_is_mbr(set, data))
		return 1;
	return list_ins_next(set, NULL, data);
}
/************************************************************************
Theset_removeoperation removes a member from a set by traversing it usinglist_
nextuntilmatchdetermines that the member to be removed has been found (see
Example 7-2). The pointerprevpoints just before the member to be removed
since this is required by list_rem_next. The list_rem_next operation setsdatato
point to the data from the member removed.
The runtime complexity ofset_remove is O(n), where nis the number of elements 
in the set. This is because, in the worst case, the entire set must be traversed 
in order to find the member to be removed. This results inntimes O(1),
the cost of the statements within the loop, for a running time of O(n) overall.
Once the member is found,list_rem_nextremoves it inO(1) time.
************************************************************************/
int set_remove(Set* set, void** data)
{
	ListElmt	*element,
				*prev;
	prev = NULL;			//to strore the right's previous element 
	for (element = list_head(set);element != NULL; element = list_next(element))
	{
		if (list_match(set, list_data(element), *data))
		{
			break;
		}
		prev = element;			//must outside of "if"
	}
	if (NULL == element)			//not in the set
	{
		return -1;
	}

	return list_rmv_next(set, prev, data);
}
/************************************************************************
Theset_union operation builds a set,setu, which is the union of the sets set1
andset2(see Example 7-2). First, setu is initialized by calling set_create. Next, the
members ofset1are inserted into setu by callinglist_ins_next repeatedly for
each member ofset1. Finally, the members of set2are inserted into setu in a
similar manner except thatset_is_memberis called before each insertion to ensure
that no members are duplicated in setu.
The runtime complexity ofset_unionis O(mn), where m is the size of set1andn
is the size of set2. In the first loop, each member of set1is traversed and
inserted into setu, which results in a running time of O(m). In the second loop,
each element ofset2is traversed, which results in n times the cost of the statements 
within this loop. This loop contains theO(m) operation set_is_member.
Therefore, the overall complexity of the loop isO(mn). Since the two loops are
executed one after another, the complexity ofset_union is the more expensive of
the two, or O(mn).
************************************************************************/
int set_union(Set* setu, \
			  const Set* set1, const Set* set2)
{
	ListElmt	*element;

	for (element=list_head(set1);element!=NULL;element=list_next(element))
	{	/* insert set1's element into setu */
		if (list_ins_next(setu,NULL,list_data(element))==-1)
			return -1;
	}
	for (element=list_head(set2);element!=NULL;element=list_next(element))
	{	/* insert set2's element into setu if it isn't in setu */
		if (!set_is_mbr(setu, list_data(element)))
			if (list_ins_next(setu,NULL,list_data(element))==-1)
				return -1;
	}

	return 0;
}
int set_intersection(Set* seti, \
					 const Set* set1, const Set* set2)
{
	ListElmt	*element;

	for (element=list_head(set1);element!=NULL;element=list_next(element))
	{	/* insert set1's element which set2 contains into seti */
		if (set_is_mbr(set2, list_data(element)))
		{
			if (list_ins_next(seti,NULL,list_data(element))==-1)
				return -1;
		}
	}
	return 0;
}
int set_difference(Set* setd, \
				   const Set* set1, const Set* set2)
{
	ListElmt* element;
	for (element=list_head(set1);element!=NULL;element=list_next(element))
	{	/* insert set1's element which set2 doesn't contain into setd */
		if ( !set_is_mbr(set2, list_data(element)))
		{
			if (list_ins_next(setd,NULL,list_data(element))==-1)
				return -1;
		}
	}
	return 0;
}
/************************************************************************
Theset_is_member operation determines whether a particular member exists in a
set (see Example 7-2). This is accomplished by traversing the set using list_next
until either a member matchingdatais found or all members are traversed.
The runtime complexity ofset_is_memberis O(n), wherenis the number of members
in the set. This is because, in the worst case, the entire set must be traversed
to find the member for which we are searching.
************************************************************************/
int set_is_mbr(const Set* set, \
			   const void* data)
{
	ListElmt* element;
	/* traverse the set with element */
	for (element=list_head(set);element!=NULL;element=list_next(element))
	{
		if ( list_match(set, list_data(element), data) )
			return 1;
	}
	return 0;
}
/************************************************************************
The set_is_subset operation determines whether one set, set1, is a subset of
another set,set2(see Example 7-2). Since a set that is a subset of another must
be the same size or smaller, we begin by comparing sizes. If this test fails, then
set1is not a subset of set2. Otherwise, set1is traversed using list_next until
either a member of set1that is not in set2is found or all members are traversed. 
If we find a member ofset1not inset2, then set1is not a subset of
set2. If we end up traversing all members of set1, then set1is a subset of set2.
The runtime complexity ofset_is_subset is O(mn), where mis the size of set1
andnis the size of set2. This is because for each member in set1, the O(n)
operationset_is_memberis called to determine whether the member is in set2.
************************************************************************/
int set_is_subset(const Set* set, \
				  const Set* subset)
{
	ListElmt *subelement;
	if (set_size(set) < set_size(subset))
		return 0;
	/* traverse the subset's element */
	for (subelement = list_head(subset);subelement!=NULL;subelement=list_next(subelement))
	{
		if ( !set_is_mbr(set ,list_data(subelement)) )
			return 0;
	}
	return 1;
}
/************************************************************************
Theset_is_equal operation determines whether one set,set1, is equal to another
set,set2(see Example 7-2). Since two sets that are equal must be the same size,
we begin by comparing sizes. If the two sets are not the same size, then they are
not equal. If the two sets are the same size, we need only return the result of
whetherset1is a subset of set2. This is determined by calling set_is_subset.
The runtime complexity ofset_is_equalis O(mn), wheremis the size of set1and
nis the size of set2. This is because set_is_subsetruns inO(mn) time.
************************************************************************/
int set_is_equal(const Set* set1, \
				 const Set* set2)
{
	if(set_size(set1) != set_size(set2))
		return 0;
	return set_is_subset(set1,set2);
}
/************************************************************************
This macro evaluates to the size of a set (see Example 7-1). It works by accessing
the size member of the Set structure.
The runtime complexity ofset_sizeis O(1) because accessing a member of a structure 
is a simple task that runs in a constant amount of time.
************************************************************************/
int set_size(const Set* set)
{
	return list_size(set);
}

void set_debug(const Set* set)
{
	ListElmt* elemt = NULL;

	if (list_size(set) > 0)
	{
		printf("head:");
		for (elemt = list_head(set);elemt != NULL;elemt=list_next(elemt))
		{
			printf("%d->", *(int*)list_data(elemt));
		}
		printf("NULL \n");
	}
}